package Solution.problem077;

import java.util.ArrayList;
import java.util.List;

/**
 * @program Leetcode
 * @description:
 * 给出一个n和k,要求求出由n中k个不同的数组成是序列，序列为升序排序。
 * 这道题要求所有可能的情况，显然我们可以使用回溯的方法求解，
 * 对于每次判断的边界条件为：后面的数要大于前面的数。而且由于这里1到n肯定是递增的，所以继续进行下一层运算的条件可以为 当前位置后面的数。具体看代码实现。
 * 深度有限搜索
 *
 * @author: lishangsheng
 * @create: 2019/06/12 20:06
 */
public class Solution {
    List<List<Integer>> res;

    public List<List<Integer>> combine(int n, int k) {
        res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        dfs(tmp, n, k, 1);
        return res;
    }

    /**
     * @param tmp 中间彼岸量
     * @param n   总数
     * @param k   需要k个数
     * @param m   添加值开始值
     */
    private void dfs(List<Integer> tmp, int n, int k, int m) {
        /*是否放够了k个数*/
        if (k == 0) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = m; i <= n; i++) {
            tmp.add(i);
            dfs(tmp, n, k - 1, i + 1);
            tmp.remove(tmp.size() - 1);
        }
    }
}
